Exercise: Sorting Algorithms

Implement an updated version of the merge-sort algorithm.

We'll cover the following

Task#

Implement a version of the merge-sort algorithm that sorts a DLList without using an auxiliary array.

Sample input

The sample input will be as follows:

5 2 9 1 3 6

Expected output

The expected output will be as follows:

Original List: 5 2 9 1 3 6 
Sorted List: 1 2 3 5 6 9 

Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.

Good luck!

svg viewer

Note: You must implement the method add(), merge_sort(), _merge_sort(Node head), and _merge(Node left, Node right) in the below code starting at line 12.

Implementation of merge-sort using DLList

Discussion on Sorting Algorithms

Solution: Sorting Algorithms